package SubjectTree.Two;

import java.util.Deque;
import java.util.LinkedList;

import Utility.TreeNode;

public class MinDepth {

/**
 * 难度：简单
 * 
 * 111. 二叉树的最小深度
 * 	给定一个二叉树，找出其最小深度。
 * 	最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 * 	
 * 说明：叶子节点是指没有子节点的节点。
 * 	
 * 示例 1：
 * 	输入：root = [3,9,20,null,null,15,7]
 * 	输出：2
 * 	
 * 示例 2：
 * 	输入：root = [2,null,3,null,4,null,5,null,6]
 * 	输出：5
 * 	
 * 提示：
 * 	树中节点数的范围在 [0, 105] 内
 * 	-1000 <= Node.val <= 1000
 *
 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		MinDepth md = new MinDepth();
		System.out.println(md.minDepth1(TreeNode.MkTree("[2,null,3,null,null,null,4,null,null,null,null,null,null,null,5,null,null,null,null,null,null,null,null,null,null,null,6]")));
	}
	//自己写（逐层遍历）
	public int minDepth(TreeNode root) {
		if(root == null)return 0;
		Deque<TreeNode> deque = new LinkedList<>();
		deque.offer(root);
		int count = 0;
		while(!deque.isEmpty()) {
			boolean flag = false;
			int currentLevelSize = deque.size();
			for(int i=0;i<currentLevelSize;i++) {
				TreeNode node = deque.poll();
				// 当左右孩子都为空的时候，说明是最低点的一层了，退出
				if(node.left==null && node.right==null) {
					flag = true;
					break;
				}
				if(node.left!=null)deque.offer(node.left);
				if(node.right!=null)deque.offer(node.right);
			}
			count++;
			if(flag)break;
		}
		return count;
	}
	//自己写（递归,使用后续遍历）
	public int minDepth1(TreeNode root) {
		if(root == null)return 0;
		int leftDepth = minDepth1(root.left);
		int rightDepth = minDepth1(root.right);
		if(root.left==null && root.right!=null)return 1+rightDepth;
		if(root.left!=null && root.right==null)return 1+leftDepth;
		int result = 1+Math.min(leftDepth, rightDepth);
		return result;
    }
	
}
